package com.zlsy.learning.leetcode.linkedlist.l234;

/**
 * @author zhouliang
 * @date 2020/8/3 20:04 单链表反转
 */
public class SingleLinkedListInversion {
  /**
   * 单链表反转-头插入，代码分析
   *
   * @param head
   * @return
   */
  public static ListNode reverseList2(ListNode head) {
    ListNode dummy = new ListNode(-1);
    ListNode pCur = head;
    while (pCur != null) {
      ListNode pNex = pCur.next;
      // 头插入法：这段代码意思就是，把dummy链表的除开头后面的节点放到当前链表除开头节点后面。
      // 我们以第一次变化举例：比如 pCur=1、2、3、4；dummy=-1、null，经过这段第一次后变成：1、null
      pCur.next = dummy.next;
      // dummy重新指向：当前（第一次变化）已知dummy=-1，null；pCur=1、null。
      // 所以把dummy除开头的位置用头插完成的数据（pCur.next = dummy.next）替换掉，即变成了：（-1,1，null）
      dummy.next = pCur;
      // 因为我们已经完成了一个节点的变化，pCur应该=下个节点以后的数据，所以也是我们一开始就存储pNex的原因
      pCur = pNex;
    }
    return dummy.next;
  }

  public static ListNode reverseList(ListNode head) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy.next;
    ListNode pCur = prev.next;
    while (pCur != null) {
      prev.next = pCur.next;
      pCur.next = dummy.next;
      dummy.next = pCur;
      pCur = prev.next;
    }
    return dummy.next;
  }

  /** 单链表 - 原地发转 */
  public static ListNode reverseList7(ListNode head) {
    ListNode prev = head;
    ListNode pCur = head.next;
    while (pCur != null) {
      // 摘掉这次要放入链表头节点的值
      prev.next = pCur.next;
      // 放入头节点
      pCur.next = head;
      // 把这次变化好的顺序重新赋值给我们的链表
      head = pCur;
      // 因为prev本次连接需要变化的值以及被删除，所以prev.next就是下次需要再变化的值
      pCur = prev.next;
    }
    return head;
  }

  public static void main(String[] args) {
    ListNode listNode = null;
    for (int i = 0; i < 5; i++) {
      if (listNode == null) {
        listNode = new ListNode(i);
      } else {
        listNode.add(i);
      }
    }
    listNode.print();
    System.err.println("---------------------------------------------");

    ListNode listNode1 = reverseList3(listNode);
    listNode1.print();
  }

  /** leetcode - 回文链表习题：头插入法 */
  private static ListNode reverseList3(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
      ListNode nextTemp = curr.next;
      // 链表当前值保留头0、1、2、3、4、null → null = 0、null
      curr.next = prev;
      // prev = 0、null
      prev = curr;
      // 下次要变化的值 1、2、3、4
      curr = nextTemp;
    }
    return prev;
  }
}
